package com.yhq.basic.algorithm.array;

import java.util.Arrays;

/**
 * @author hqyin
 * @date 2023/8/22 3:32 下午
 */
public class TestArray {
    public static void main(String[] args) {
        int[] arr1 = {9,2,1,5,7,4,8,6,3};
        for (int i = 0; i < arr1.length-1; i++) {
           int end = i;
           int tmp = arr1[end+1];
           while (end>=0) {
               if(tmp<arr1[end]){
                   arr1[end+1]=arr1[end];
                   arr1[end] = tmp;
                   end--;
               }else {
                   break;
               }
           }
        }
        System.out.println(Arrays.toString(arr1));
        //插入排序
//        insert_sort(arr1);
        //希尔排序
//        shell_sort(arr1, 3);
        //测试冒泡排序算法
//        test_bubbleSort(arr1,false);
//        System.out.println(Arrays.toString(arr1));

        //测试选择排序
//        test_sectionSort(arr1,true);
//        System.out.println(Arrays.toString(arr1));

        // 归并排序
//        mergeSort(arr1, 0, arr1.length - 1);
//        System.out.println(Arrays.toString(arr1));

        //快速排序
//        quickSort(arr1);


        //测试二维数组寻址地址计算公式
        //test_twoArray();

        //两数之和
//        int[] arr = {1, 3, 5, 7};
        //test_twoSum(arr,10);

        //寻找两个正序数组的中位数
//        int[] m1 = {1, 3};
//        int[] m2 = {2};
//        System.out.println(test_median(m1,m2));;


    }

    private static void shell_sort(int[] arr1, int gap) {
        System.out.println("排序前："+Arrays.toString(arr1));
        while (gap>1) {
            //gap/2
            gap = gap/3+1;
            for(int j=0;j<gap;j++){
                for (int i = j; i < arr1.length - gap; i += gap) {
                    int end = i;
                    int tmp = arr1[end + gap];
                    while (end >= 0) {
                        if (tmp < arr1[end]) {
                            arr1[end + gap] = arr1[end];
                            end-=gap;
                        }else{
                            break;
                        }
                    }
                    arr1[end + gap] = tmp;
                }
            }
        }
        System.out.println("排序后："+Arrays.toString(arr1));
    }

    private static void insert_sort(int[] arr1) {
        for (int i = 0; i < arr1.length - 1; i++) {
            int end = i;
            int tmp = arr1[end + 1];
            while (end >= 0) {
                if (tmp < arr1[end]) {
                    arr1[end + 1] = arr1[end];
                    end--;
                } else {
                    break;
                }

            }
            arr1[end + 1] = tmp;
        }
        System.out.println(Arrays.toString(arr1));
    }

    /**
     * 从数列中挑出一个元素，称为"基准"（pivot），
     * 重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任何一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
     *
     * @param arr
     */
    private static void quickSort(int[] arr) {

        for (int i = 0; i < arr.length; i++) {
            int tmp = arr[i];
            for (int j = 0; i < arr.length; j++) {

            }
        }
    }

    private static void mergeSort(int[] arr, int s, int e) {
        if (s < e) {
            //start == end ,不需要分割
            int m = (s + e) / 2;
            mergeSort(arr, s, m);
            mergeSort(arr, m + 1, e);
            mergeSort(arr, s, m, e);
        }
    }

    private static void mergeSort(int[] arr, int s, int m, int e) {
        int[] tmp = new int[e - s + 1];
        int i = s;
        int j = m + 1;
        int k = 0;
        while (i <= m && j <= e) {
            tmp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
        }

        while (i <= m) {
            tmp[k++] = arr[i++];
        }

        while (j <= e) {
            tmp[k++] = arr[j++];
        }

        for (int t = 0; t < k; t++) {
            arr[s + t] = tmp[t];
        }

    }

    /**
     * 在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
     * 从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
     * 重复第二步，直到所有元素均排序完毕。
     *
     * @param arr1
     * @param asc
     */
    private static void test_sectionSort(int[] arr1, boolean asc) {
        for (int i = 0; i < arr1.length-1; i++) {
            for (int j = i + 1; j < arr1.length; j++) {
                if (asc) {
                    if (arr1[i] > arr1[j]) {
                        int tmp = arr1[i];
                        arr1[i] = arr1[j];
                        arr1[j] = tmp;
                    }
                } else {
                    if (arr1[i] < arr1[j]) {
                        int tmp = arr1[i];
                        arr1[i] = arr1[j];
                        arr1[j] = tmp;
                    }
                }
            }
        }
    }

    /**
     * 冒泡排序:顺序排序，第一个比第二个大就交互顺序等等
     * 5，7，1，3
     * 一 5，1，3，7；
     * 4-1-0  n-1 - (0+(n-1)*1)
     * 4-1-1  0+(2-1)*1
     * 4-1-2
     * 4-1-3
     * <p>
     * 二 1，3，5，7；
     * j(0~2)
     * <p>
     * J(0~1)
     *
     * @param arr1
     * @param asc  true 顺序排序，false 逆序排序
     */
    private static void test_bubbleSort(int[] arr1, boolean asc) {
        for (int i = 0; i < arr1.length; i++) { // n
            for (int j = 0; j < arr1.length - 1 - i; j++) { //n-1-(n
                if (asc) {
                    if (arr1[j] > arr1[j + 1]) {
                        int tmp = arr1[j];
                        arr1[j] = arr1[j + 1];
                        arr1[j + 1] = tmp;
                    }
                } else {
                    if (arr1[j] < arr1[j + 1]) {
                        int tmp = arr1[j];
                        arr1[j] = arr1[j + 1];
                        arr1[j + 1] = tmp;
                    }
                }

            }
        }
    }

    /**
     * 给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
     *
     * 算法的时间复杂度应该为 O(log (m+n)) 。
     *
     *
     *
     * 示例 1：
     *
     * 输入：nums1 = [1,3], nums2 = [2]
     *
     * 输出：2.00000
     * 解释：合并数组 = [1,2,3] ，中位数 2
     *
     * 示例 2：
     *
     * 输入：nums1 = [1,2], nums2 = [3,4]
     * 输出：2.50000
     * 解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
     * @param m1
     * @param m2
     * @return
     */
//    private static double test_median(int[] m1, int[] m2) {
//        int length = m1.length+m2.length;
//        int half = length/2;
//
//
//
//    }

    /**
     * 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。
     * 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
     * 你可以按任意顺序返回答案。
     * 输入：nums = [2,7,11,15], target = 9
     * 输出：[0,1]
     * 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
     *
     * @param arr
     * @param target
     */
//    private static void test_twoSum(int[] arr, int target) {
//        for (int i = 0; i < arr.length-1; i++) {
//            if
//
//        }
//    }
    private static void test_twoArray() {
        Object[][] ar = new Object[3][3];
        ar[0][0] = new Object();
        ar[0][1] = new Object();
        ar[0][2] = new Object();

        ar[1][0] = new Object();
        ar[1][1] = new Object();
        ar[1][2] = new Object();

        ar[2][0] = new Object();
        ar[2][1] = new Object();
        ar[2][2] = new Object();

        System.out.println(System.identityHashCode(ar[0][0]));
        System.out.println(System.identityHashCode(ar[0][1]));
    }
}
